import csv
import math
import numpy as np
import networkx as nx
import random
from itertools import islice
class Node:
    def __init__(self,name=None,value=None, node_type=0):
        self.name=name
        self.value=value
        self.node_type = node_type
        self.left=None
        self.right=None
        self.code = ''
        self.thita = None

class huffmanTree:
    def __init__(self, root = None, nodeNum = 0, leafNum = 0, ceilings = 0):
        self.root = root
        self.nodeNum = nodeNum
        self.leafNum = leafNum
        self.ceillings = ceilings

    def buildHuffTree(self, nodes,theta_w):
        '''
        构造huffman树
        :param nodes 候选节点，节点结构为节点关键字，节点权值，节点类型0：叶子节点，1非叶子节点
        :return:
        '''
        huffNodes = [Node(field[0], field[1]) for field in nodes]
        huffNodes.sort(key=lambda node: node.value, reverse=True)
        leafNum = len(huffNodes)
        nodeNum = leafNum
        while len(huffNodes) > 1:

            newNode = Node(value=huffNodes[-1].value + huffNodes[-2].value, node_type=1)
            print(huffNodes[-1].name,':',huffNodes[-1].value,' || ',huffNodes[-2].name,':'+str(huffNodes[-2].value))
            newNode.thita = np.array(np.random.random_sample(theta_w))
            nodeNum += 1
            newNode.left = huffNodes.pop(-1)
            newNode.right = huffNodes.pop(-1)
            insertNewNode(newNode, huffNodes)
        self.root = huffNodes[0]
        self.nodeNum = nodeNum
        self.leafNum = leafNum
        self.ceillings = math.ceil(math.log(nodeNum, 2))
        # self.path = [0] * self.ceillings
        return huffNodes[0]
def insertNewNode(newNode, huffNodes):
    '''
    将新生成的节点插入原huff序列中
    param newNode:
    :param huffNodes:
    :return:
    '''
    if len(huffNodes) <= 0:
        huffNodes.append(newNode)
        return
    start = 0
    end = len(huffNodes)-1
    insertLoc = 0
    while start <= end:
        mid = math.floor((start + end) / 2)
        if huffNodes[mid].value < newNode.value:#往左寻找插入位置
            if mid == start:
                insertLoc = start
                huffNodes.insert(insertLoc, newNode)
                break
            else:
                if huffNodes[mid - 1].value >= newNode.value:#找到往左的插入位置
                    insertLoc = mid
                    huffNodes.insert(insertLoc, newNode)
                    break
                else:
                    end = mid - 1
        elif huffNodes[mid].value == newNode.value:
            insertLoc = mid
            huffNodes.insert(insertLoc, newNode)
            break
        else:
            if mid == end:
                huffNodes.append(newNode)
                break
            else:
                if huffNodes[mid + 1].value <= newNode.value:#在右方向找到插入位置
                    insertLoc = mid + 1
                    huffNodes.insert(insertLoc, newNode)
                    break
                else:
                    start = mid + 1



codeDic1 = {}
codeDic2 = {}
# 由哈夫曼树得到哈夫曼编码表
def HuffmanCodeDic(head, x=''):
    '''
    由哈夫曼树得到哈夫曼编码表
    :param head: 根节点
    :param x:
    :return:
    '''
    if head:
        HuffmanCodeDic(head.left, x + '1')
        head.code += x
        if head.name:
            codeDic2[head.code] = head.name
            codeDic1[head.name] = head.code
        HuffmanCodeDic(head.right, x + '0')

def build_graph_from_file(datadir):
    '''
            使用networkx构建图结构，
            :param G:
            :param file_:
            :param delimiter_:
            :return:
            '''
    g = nx.Graph()
    reader = csv.reader(open(datadir), delimiter=' ')
    index = 0
    for line in reader:
        '''
        desc：跳过表头
        '''
        # elif index <=10000:
        #     index += 1
        # else:
        #     break
        g.add_edge(int(line[0]), int(line[1]))
    return g
def build_graph_from_file_yutube(datadir):
    '''
            使用networkx构建图结构，
            :param G:
            :param file_:
            :param delimiter_:
            :return:
            '''
    reader = csv.reader(open(datadir), delimiter='	')
    index = 0
    g = nx.Graph()
    for line in reader:
        '''
        desc：跳过表头
        '''
        # elif index <=10000:
        #     index += 1
        # else:
        #     break
        if index < 4:
            index += 1
            continue
        g.add_edge(int(line[0]), int(line[1]))
    return g

def build_graph_from_file_yutube1(datadir):
    '''
            使用networkx构建图结构，
            :param G:
            :param file_:
            :param delimiter_:
            :return:
            '''
    reader = csv.reader(open(datadir), delimiter=',')
    index = 0
    g = nx.Graph()
    for line in reader:
        g.add_edge(int(line[0]), int(line[1]))
    return g

def Sigmoid(x):
    '''
    definition of sigmoid function and it's derivation
    '''
    from math import exp
    return 1.0 / (1.0 + exp(-x))


def SigmoidDerivate(y):
    return y * (1 - y)


def Tanh(x):
    '''
    definition of sigmoid function and it's derivation
    '''
    from math import tanh
    return tanh(x)


def TanhDerivate(y):
    return 1 - y * y
def calSim(v1, v2, structureMatrix, ab_set):
    '''
    计算两个向量的相似度
    :param v1:
    :param v2:
    :param structureMatrix:节点结构特征矩阵
    :param ab_set:无链接的节点对集合
    :return: 返回相似度值
    '''
    vct1 = np.array(structureMatrix[v1])
    vct2 = np.array(structureMatrix[v2])
    ab_sample = random.choice(ab_set)
    ab_v1 = np.array(structureMatrix[ab_sample[0]])
    ab_v2 = np.array(structureMatrix[ab_sample[1]])
    curr_edge_sim = cos_sim(vct1,vct2)
    rand_ab_sim = cos_sim(ab_v1, ab_v2)
    if curr_edge_sim > rand_ab_sim:
        return 1
    elif curr_edge_sim == rand_ab_sim:
        return 0.5
    else:
        return 0

def cos_sim(v1,v2):
    dot_product = np.dot(v1, v2.transpose())
    norm_a = np.linalg.norm(v1)
    norm_b = np.linalg.norm(v2)
    return dot_product / (norm_a * norm_b)

def cal_auc(test_set, ab_set, structureMatrix):
    '''
    计算auc,选取测试集，根据无关系的集合中随机取一对。分别计算
    :param test_set:
    :param ab_set:
    :return:
    '''
    result_auc = 0.0
    for item in test_set:
        result_auc += calSim(item[0], item[1],structureMatrix,ab_set)
    return result_auc/len(test_set)

def find_no_edge(orig_graph):
    '''
    找到没有关系的节点对
    :return:
    '''
    sep_list = []#无节点的
    edge_list = []
    node_count = len(orig_graph.nodes)
    # graph_matrix = np.ndarray((node_count,node_count), dtype=bool)
    edges = orig_graph.edges
    node_edge_list = [[i] for i in range(node_count)]
    # no_edge_list = [[] for i in range(node_count)]
    node_set = set(range(node_count))
    for item in edges:
        v1 = item[0]
        v2 = item[1]
        node_edge_list[v1].append(v2)
        node_edge_list[v2].append(v1)
        edge_list.append([v1, v2])
        edge_list.append([v2, v1])
    maxDgree = max([i[1] for i in orig_graph.degree])
    for i in range(0,node_count):
        curr_set = set(node_edge_list[i])
        no_edge_set = random.sample((node_set - curr_set), random.randint(1,maxDgree))
        tmp_list = [[i,elem] for elem in no_edge_set]
        sep_list += tmp_list
        # no_edge_list[i] = no_edge_set

    return edge_list, sep_list
def saveMatrixData(data,fileName):
    '''
    保存中间数据到文件
    :param data:
    :return:
    '''
    np.savetxt(fileName, data, fmt = "%f", delimiter = ",")

if __name__ == '__main__':
    g = build_graph_from_file('data/facebook_combined.txt')
    # g = build_graph_from_file_yutube('data/com-youtube.ungraph.txt')
    # g = build_graph_from_file_yutube1('data/youtubeCoded.csv')
    find_no_edge(g)
    exit(0)
    degreeInfo = list(g.degree)
    hfTree = huffmanTree();
    hfTree.buildHuffTree(degreeInfo,50)
    HuffmanCodeDic(hfTree.root, '')
    print(codeDic1)
    print(hfTree)